package liangtWorkSpace.simple;

import java.util.Arrays;

/**
 * @ClassName HammingWeight
 * @Description : 查询二进制中1的个数
 * @Author : LiangT
 * @Date : 2020/6/11 16:49
 */
public class HammingWeight {
    public static int reverse5(int n){
        int count = 0;
        while (n != 0){
            if ((n&1) == 1 ){
                count ++;
            }
            n>>>=1;
        }
        return count;
    }

    public int hammingWeight0(int n) {
        int count = 0;
        Integer[] integers = new Integer[32];
        for (int i = 0; i < 32; i++) {
            if (((n >>> i) & 1) == 1) {
                count++;
            }
        }
        return count;
    }

    public int hammingWeight1(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if (((n >>> i) & 1) == 1) {
                count++;
            }
        }
        return count;
    }


    public int hammingWeight2(int n) {
        int count = 0;
        while (n != 0) {
            count += n & 1;
            n = n >>> 1;
        }
        return count;
    }

    public int hammingWeight3(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & (1 << i)) != 0) {
                count++;
            }
        }
        return count;
    }

    public int hammingWeight4(int i) {
        int count = 0;
        for (int j = 0; j < 32; j++) {
            if ((i & (1 << j)) >>> j == 1)
                count++;
        }
        return count;
    }

    public int hammingWeight5(int n) {
        int count = 0;
        while (n != 0) {
            n &= n - 1;
            count++;
        }
        return count;
    }


    public int hammingWeight6(int n) {
        return n == 0 ? 0 : 1 + hammingWeight6(n & (n - 1));
    }

    public int hammingWeight7(int i) {
        //table是0到15转化为二进制时1的个数
        int table[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
        int count = 0;
        while (i != 0) {//通过每4位计算一次，求出包含1的个数
            count += table[i & 0xf];
            i >>>= 4;
        }
        return count;
    }


    public int hammingWeight8(int n) {
        n = ((n & 0xaaaaaaaa) >>> 1) + (n & 0x55555555);
        n = ((n & 0xcccccccc) >>> 2) + (n & 0x33333333);
        n = (((n & 0xf0f0f0f0) >>> 4) + (n & 0x0f0f0f0f));
        n = n + (n >>> 8);
        n = n + (n >>> 16);
        return n & 63;
    }


    public int hammingWeight9(int n) {
        n = ((n >>> 1) & 0x55555555) + (n & 0x55555555);
        n = ((n >>> 2) & 0x33333333) + (n & 0x33333333);
        n = (((n >>> 4) & 0x0f0f0f0f) + (n & 0x0f0f0f0f));
        n = n + (n >>> 8);
        n = n + (n >>> 16);
        return n & 63;
    }


    public int hammingWeight10(int n) {
        n = ((n & 0xaaaaaaaa) >>> 1) + (n & 0x55555555);
        n = ((n & 0xcccccccc) >>> 2) + (n & 0x33333333);
        n = (((n & 0xf0f0f0f0) >>> 4) + (n & 0x0f0f0f0f));
        n = (((n & 0xff00ff00) >>> 8) + (n & 0x00ff00ff));
        n = (((n & 0xffff0000) >>> 16) + (n & 0x0000ffff));
        return n;
    }


    public int hammingWeight11(int n) {
        n = (n & 0x11111111) + ((n >>> 1) & 0x11111111) + ((n >>> 2) & 0x11111111) + ((n >>> 3) & 0x11111111);
        n = (((n & 0xf0f0f0f0) >>> 4) + (n & 0x0f0f0f0f));
        n = n + (n >>> 8);
        n = n + (n >>> 16);
        return n & 63;
    }


    public int hammingWeight12(int n) {
        n = (n & 011111111111) + ((n >>> 1) & 011111111111) + ((n >>> 2) & 011111111111);
        n = ((n + (n >>> 3)) & 030707070707);
        n = ((n + (n >>> 6)) & 07700770077);
        n = ((n + (n >>> 12)) & 037700007777);
        return ((n + (n >>> 24))) & 63;
    }


    public int hammingWeight13(int n) {
        n = (n & 0x42108421) + ((n >>> 1) & 0x42108421) + ((n >>> 2) & 0x42108421) + ((n >>> 3) & 0x42108421) + ((n >>> 4) & 0x42108421);
        n = ((n + (n >>> 5)) & 0xc1f07c1f);
        n = ((n + (n >>> 10) + (n >>> 20) + (n >>> 30)) & 63);
        return n;
    }


    public int hammingWeight14(int i) {
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
    }

    public int hammingWeight15(int n) {
        n = n - ((n >>> 1) & 033333333333) - ((n >>> 2) & 011111111111);
        n = ((n + (n >>> 3)) & 030707070707);
        n = ((n + (n >>> 6)) & 07700770077);
        n = ((n + (n >>> 12)) & 037700007777);
        return ((n + (n >>> 24))) & 63;
    }

    public int hammingWeight16(int n) {
        int tmp = n - ((n >>> 1) & 0x77777777) - ((n >>> 2) & 0x33333333) - ((n >>> 3) & 0x11111111);
        tmp = ((tmp + (tmp >>> 4)) & 0x0f0f0f0f);
        tmp = ((tmp + (tmp >>> 8)) & 0x00ff00ff);
        return ((tmp + (tmp >>> 16)) & 0x0000ffff) % 63;
    }


    public int hammingWeight17(int n) {
        n = n - ((n >>> 1) & 0xdef7bdef) - ((n >>> 2) & 0xce739ce7) - ((n >>> 3) & 0xc6318c63) - ((n >>> 4) & 0x02108421);
        n = ((n + (n >>> 5)) & 0xc1f07c1f);
        n = ((n + (n >>> 10) + (n >>> 20) + (n >>> 30)) & 63);
        return n;
    }
}
